Report: Interleaving String

标签（空格分隔）： Lintcode DP Ladder

题目

• 题目链接

思考

first trial: fail

• F[i][j]表示是否可以用S1, S2的前i,j个字符表示S3的前i+j个字符. 既然是M x N的DP, 自然要先init 第一行和第一列.
• 然后就是optimally equation. 就是每次看S3的i+j-1个字符是否等于S1的i-1或者S2的j-1. 如果是, 就沿用F[i-1][j]或F[i][j-1].
• 但是这样fail在第15/18个test case:

  1

  ["sdfjas;dfjoisdufzjkndfasdkfja;sdfa;dfa;dfaskdjhfasdhjdfakhdgfkajdfasdjfgajksdfgaksdhfasdkbfjkdsfbajksdfhakjsdfbajkdfbakdjsfgaksdhgfjkdsghfkdsfgadsjfgkajsdgfkjasdfh", "dfnakdjnfjkzghdufguweygfasjkdfgb2gf8asf7tgbgasjkdfgasodf7asdgfajksdfguayfgaogfsdkagfsdhfajksdvfbgkadsghfakdsfgasduyfgajsdkfgajkdghfaksdgfuyadgfasjkdvfjsdkvfakfgauyksgfajkefgjkdasgfdjksfgadjkghfajksdfgaskdjfgasjkdgfuyaegfasdjkfgajkdfygadjskfgjkadfg", "sdfjas;dfjoisdfnakdjnfjkzghdufguwdufzjkeygfasjkdfgb2gf8asf7ndtgbgasjkdfgasodf7asdfgfajkasdksdfguayfgaogfsdkagfsfjadhfajksdvfbgkadsghfa;sdkdsfgasduyfgajsdkfgafajkdghfaksdgfuyadgfas;dfjkdvfjsdkvfakfgauyksa;dgfajkefgjkdasgfdjksffaskdjhfasdhjdfakhdgadjkghfajgfkajdfksdfgaskdjfgasjkdgfuasdjfgajksdfgaksdhfasdkbfjkdsfbajksdfyaegfasdjkfgajkdfygadjskfgjkadfghakjsdfbajkdfbakdjsfgaksdhgfjkdsghfkdsfgadsjfgkajsdgfkjasdfh"]

应该return false, 但我return true.
找了好久, 终于发现问题了: 我的递推方程是:

1
2
3
4
5
6
7
8

if (s3.charAt(i + j - 1) == s1.charAt(i - 1)) {
  F[i][j] = F[i - 1][j];
} else if (s3.charAt(i + j - 1) == s2.charAt(j - 1)) {
  F[i][j] = F[i][j - 1];
}
else {
  F[i][j] = false;
}

注意这里: 如果s1.charAt(i - 1)和s3.charAt(i + j - 1)和s2.charAt(j - 1)相等的话, F[i][j]是给else if覆盖了. 所以有时候对有时候错. 所以是我的optimally equation写错了. 这里是or的关系.

2nd trial: AC

• 这次解决了这个bug. 使用OR来得到F[i][j].

3rd trial: fail

• 虽然刚才那样做是可以AC, 但是空间复杂度太大! 因为这个只和上一层跟左一列有关系. 所以可以用1d的rolling array来做. 那为什么这里和distinct subsequences的1d不同, 是自左向右循环呢? 分析如下:
• update的时候要看是否使用更新前还是更新后的上一层的信息.
  • 例如distinct subsequences就是使用更新前的上一层信息, 所以内循环是自后往前.
  • 而像Interleaving string的1d rolling array就是自前向后.
  • 这2个有什么区别呢: 区别在于optimally equation, 看到底需要上一层的哪个数, 如果是上一层的左边, 那么就不能覆盖的循环, 所以要自后向前. 而且若是同时需要上一层左侧和这一层左侧的话就不能用1d滚动数组了, 用mod rolling.
  • 总结见下图:
• Ganer就是这样写的. 但是我一开始先是像distinct substring那样写: 即内循环是从后向前来update State. 结果是错的.
  • 所以这里有个重要事情. 什么时候是自前向后, 什么时候自后向前. 这里并不是说Top-down, Bottom-up. 而是说1d rolling array里面是使用更新前还是更新后的值.

    每次迭代我们只保存了上一行的信息。接下来从前往后还是从后往前就取决于我们要用的是更新前还是更新后的信息，如果从前往后，我们会使用更新后的信息

4th trial : AC

• 这题和distinct substring 的 rolling array的内层循环不同的是: 这里是从前往后.